"""
题目：https://leetcode-cn.com/problems/spiral-matrix/
    给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
    示例 1：
    输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
    输出：[1,2,3,6,9,8,7,4,5]
思路：模拟螺旋矩阵的路径进行输出，行列的转换使用directions矩阵获取方向的转换,directIndex知道应该是向哪一个方向转；
     同时需要准备一个visited矩阵，同输入矩阵完全一致，用来指示某个数字是否被访问过，visited的初始值都是False，值为True表示当前位置的值被访问过；
     之后就是更新行列索引rowIndex,colIndex,并将新的行列索引对应的数字填到最终结果rtn里即可。
时间复杂度：O(mn)
空间复杂度：O(mn)
"""
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix or not matrix[0]:
            return matrix
        rows,cols = len(matrix),len(matrix[0])
        visited = [[False] * cols for _ in range(rows)]
        # 方向转换矩阵
        directions = [[0,1],[1,0],[0,-1],[-1,0]]
        # 当前行列索引
        rowIndex,colIndex = 0, 0
        # rtn中共有total个数字
        total = rows * cols
        # 方向转换矩阵的索引，指引是向右、向下、向左还是向上转换
        directIndex = 0
        rtn = []
        for i in range(total):
            # 当前数字放到返回的列表rtn中
            rtn.append(matrix[rowIndex][colIndex])
            # 更新当前行列索引对应的数字已被访问
            visited[rowIndex][colIndex] = True
            # 更新下一次需要访问的行列索引
            nextRow,nextCol = rowIndex + directions[directIndex][0],colIndex + directions[directIndex][1]
            # 判断下一次需要访问的行列索引是否合理，如果不合理的话，需要按照方向转换矩阵的指示更新方向
            if not (0 <= nextRow < rows and 0 <= nextCol < cols and not visited[nextRow][nextCol]):
                directIndex = (directIndex + 1) % 4
            # 更新行列索引
            rowIndex += directions[directIndex][0]
            colIndex += directions[directIndex][1]
        return rtn
            
